package 力扣日常刷题.木22一月.第03天0110;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/10
 * @description
 * https://leetcode-cn.com/problems/power-set-lcci/
 */
public class Demo02回溯中等幂集 {


    List<List<Integer>> res;
    public List<List<Integer>> subsets1(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        res.add(list);
        dfs(0,nums,list);
        return res;
    }

    public void dfs(int u,int[] nums,ArrayList<Integer> list ){
        if(u==nums.length)return;

        for (int i = u; i < nums.length; i++) {
            list.add(nums[i]);
            res.add(list);
            dfs(u+1,nums,list);
            list.remove(list.indexOf(nums[i]));
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int n = nums.length;
        //数组长度为n 则有2的n次方个子集 每次检查最低为

        for (int i = 0; i < Math.pow(2,n); i++) {
            List<Integer> list = new ArrayList<>();
            int v = i;
            int j = n;
            while (j -- > 0){
                if ((v & 1) == 1)
                    list.add(nums[j]);
                v >>= 1;
            }
            lists.add(list);
        }
        return lists;
    }


}
